

/**
 * 给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串（重复字符算做不同字符）。
 * <p>
 * 示例：
 * <p>
 * 输入: S = "ADOBECODEBANC", T = "ABC"
 * 输出: "BANC"
 * 说明：
 * <p>
 * 如果 S 中不存这样的子串，则返回空字符串 ""。
 * 如果 S 中存在这样的子串，我们保证它是唯一的答案。
 */
class Solution {

    public static void main(String[] args) {
        //System.out.println(minWindow("ADOBECODEBANC", "ABC"));
        //System.out.println(minWindow("cabwefgewcwaefgcf", "cae"));
        //System.out.println(minWindow("ezsevejszgvxqqggbwkxpwzoyrbaslnxmfdjmmentzllptsspeshatvbkwbcjozwwcfirjxmiixadrsvwmcyfzzpxauhptdlyivrssdadacisxdojhopgogeoalfwoswypnqiqtnqxvkubaeiptpdzvtaizywtuwjhptxkgnhdaceagppbeuabocjpahiudrdskacsqmwqocqurivxcxyqcjfcqqzwheqsfvkxhinvlfrenmcslcinoqsggtcpxtjcowbveosrwjyjvcbigmwueobmjdbgynlojmjpbbjzmhkjjosraomgepsnuvvtkghtttlwwuxjdhsovmfvctdiixxdvtyfzhbuamszipklxezsrgqtavcitzloulvwtwqvklwscgfznguenmzphdxcdlqxwotrkmnxzjrbsxdffxlslkhsohxtupsqdokqaxnzieccdfhjesdpfnktuhoqwgicussurhvalaerfmakgfznslioswerdntxfnuxurzhrfyzrajagkpywypqutjzicxqrtplkqtevtdpuoraagayeppblyavdzluscifsblowqdqeuqectdjkukxumtzogwijenbhapdquuwqmbthgcscmpyaiyorwxaambjntmfnicexfzenbyppoppyngpjdplrtugojmbtqhsvixkjxbylqqmgwbpbtdsozzcinfedpwaxvkhtnhgdxsjtwburephdojodouifqkdowmjjtpmrkwmizjzdygioryrhsznllqbhekqxbeqlcdtbougmcpavptdkuqvfiymmieljkcxnhsovpvjrmjnbcqlwiidsirgqvrcfvbuctlzigicutrxxjlvrvylerrwmkaugbqkxbkhjujdqcdplolejlpndimrtmnzoelnfvupsgukixzwlkaxysmbayuvliubogotdkkxqhhbejxsvxrtpdwsetnrb", "ksrsimxsxxjegkkpj"));
        System.out.println(minWindow("ccacacaccaaaacccc", "aaaa"));
    }

    /**
     * 签名算法
     *
     * @param s
     * @param t
     * @return
     */
    public static String minWindow(String s, String t) {
        if (s.length() < t.length()) {
            return "";
        }
        int[] sign = sign(t, 0, t.length());
        int[] tmp = sign(s, 0, s.length());
        if (match(sign, tmp)) {
            dp = new int[s.length()][s.length() + 1][3];
            int[] res = min(s, 0, s.length(), sign, t, t.length());
            return s.substring(res[1], res[2]);
        }
        return "";
    }

    private static int[][][] dp;
    private static int sum = 0;

    private static int[] min(String s, int start, int end, int[] sign, String t, int len) {
        if (end - start < len || start >= s.length()) {
            int[] res = new int[3];
            res[0] = Integer.MAX_VALUE;
            return res;
        }
        if (dp[start][end][0] != 0) {
            return dp[start][end];
        }
        int[] res = new int[3];
        int[] tmp = sign(s, start, end);
        // 判断当前是否满足
        if (!match(sign, tmp)) {
            res[0] = Integer.MAX_VALUE;
            dp[start][end] = res;
            return res;
        }
        // 如果满足，则迭代下去
        // 找到可以增加的位数
        int add = 0;
        for (; add < end; add++) {
            if (t.indexOf(s.charAt(start + add)) != -1) {
                add++;
                break;
            }
        }
        // 找到可以减少的位数
        int del = 0;
        for (; del < end; del++) {
            if (t.indexOf(s.charAt(end - 1 - del)) != -1) {
                del++;
                break;
            }
        }
        int[] res1 = min(s, start + add, end, sign, t, len);
        int[] res2 = min(s, start, end - del, sign, t, len);
        if (res1[0] == Integer.MAX_VALUE && res2[0] == Integer.MAX_VALUE) {
            // 如果不能再减少了
            res[1] = start + add - 1;
            res[2] = end - del + 1;
            res[0] = res[2] - res[1];
        } else if (res1[0] <= res2[0]) {
            res[0] = res1[2] - res1[1];
            res[1] = res1[1];
            res[2] = res1[2];
        } else {
            res[0] = res2[2] - res2[1];
            res[1] = res2[1];
            res[2] = res2[2];
        }
        dp[start][end] = res;
        return res;
    }

    private static int[] sign(String s, int start, int end) {
        int[] sign = new int[128];
        for (int i = start; i < end; i++) {
            sign[s.charAt(i)] += 1;
        }
        return sign;
    }

    private static boolean match(int[] sign, int[] tmp) {
        for (int i = 0; i < sign.length; i++) {
            if (sign[i] != 0) {
                if (sign[i] > tmp[i]) {
                    return false;
                }
            }
        }
        return true;
    }

}